function insertValueSearch(arr, key, low, height) {
  low = low || arr[0]
  low = low < 0 ? 0 : low
  height = height || arr[arr.length - 1]
  height--;
  if (low > height) {
    return -1;
  }
  var mid = Math.floor((low + height) / 2);
  if (arr[mid] == key) {
    return mid;
  } else if (arr[mid] < key) {
    low = mid + 1
    return insertValueSearch(arr, key, low, height);
  } else {
    mid = height - 1;
    return insertValueSearch(arr, key, low, height);
  }
}
// 递归
const testArr = [2, 1, 10, 8, 5, 4, 3, 9, 6, 0, -1, -2, 2 * 1, 3 * -1, 1 - 5, 7]
testArr.sort((a, b) => {
  return a - b
})
console.log(testArr);
console.log(insertValueSearch(testArr, -1));

// * 插值查找是对二分查找的进一步改进
// * 不支持浮点数
// 1.对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
// * 关键字分布不均匀的情况下，该方法不一定比折半查找要好
// * 差别就是low和height，一个是函数传入的，一个是作为动态变量存储的